//
// Created by 天亮 on 2022/11/21.
//

// 快排代码默写版
void Qsort(int A[], int L, int R) {
    if (L >= R) return;         // 若排序区间内元素个数小于1，则退出
    int i = L, j = R;           // i和j是数组的两个游标
    // 数组待排序区间内随机一个数与A[L]交换位置       // 优化快排
    int key = A[L];             // key作为枢值参与比较
    while (i < j) {
        while (i<j && A[j]>key)
            j--;
        while (i<j && A[i]<=key)
            i++;
        if (i<j)
            swap(A[i], A[j]);   // 交换A[i]和A[j]的位置
    }
    A[i] = key;                 // 确定枢值的位置
    Qsort(A, L, i-1);           // 递归处理左区间
    Qsort(A, i+1, R);           // 递归处理右区间
    return;
}
